package com.le.enhance.class8;

import org.junit.Test;

/**
 * Bob的生存概率
 * 【题目】
 * 给定五个参数n,m,i,j,k。表示在一个N*M的区域，Bob处在(i,j)点,每次Bob等概率的向上、 下、左、右四个方向移动一步，
 * Bob必须走K步。如果走完之后，Bob还停留在这个区域上，就算Bob存活，否则就算Bob死亡。
 * 请求解 Bob的生存概率，返回字符串表示[分数]的方式
 * ====> 总的存活方法数/ 4的k次幂
 */
public class Code_05_BobDie {
    public static String bob1(int N, int M, int i, int j, int K) {
        // 共有4的k子幂方法
        long all = (long) Math.pow(4, K);
        long live = process(N, M, i, j, K);
        long gcd = gcd(all, live);
        return String.valueOf((live / gcd) + "/" + (all / gcd));
    }

    // 存活方法数
    private static long process(int n, int m, int i, int j, int k) {
        if (i < 0 || i == n || j < 0 || j == m) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        return process(n, m, i, j + 1, k - 1) +
                process(n, m, i, j - 1, k - 1) +
                process(n, m, i - 1, j, k - 1) +
                process(n, m, i + 1, j, k - 1);
    }

    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }

    // dp
    public static String bob2(int N, int M, int i, int j, int K) {
        int[][][] dp = new int[N + 2][M + 2][K + 1];
        // k == 0 的所有都为1
        for (int row = 1; row <= N; row++) {
            for (int col = 1; col <= M; col++) {
                dp[row][col][0] = 1;
            }
        }
        for (int rest = 1; rest <= K; rest++) {
            for (int row = 1; row <= N; row++) {
                for (int col = 1; col <= M; col++) {
                    // 每个位置都依赖于上下左右四个位置
                    dp[row][col][rest] = dp[row - 1][col][rest - 1];
                    dp[row][col][rest] += dp[row + 1][col][rest - 1];
                    dp[row][col][rest] += dp[row][col - 1][rest - 1];
                    dp[row][col][rest] += dp[row][col + 1][rest - 1];
                }
            }
        }
        long all = (long) Math.pow(4, K);
        long live = dp[i + 1][j + 1][K];
        long gcd = gcd(all, live);
        return String.valueOf((live / gcd) + "/" + (all / gcd));
    }

    @Test
    public void test() {
        int N = 10;
        int M = 10;
        int i = 3;
        int j = 2;
        int K = 5;
        System.out.println(bob1(N, M, i, j, K));
        System.out.println(bob2(N, M, i, j, K));
    }
}
